package top.minuy.subject.leetcode.mst_17_14;

import java.util.Arrays;
import java.util.Random;
/**
 * @author Minuy
 * @time 10:04
 * @date 2021/9/2
 */
public class Solution {
    public int[] smallestK(int[] arr, int k) {
        if(k>=arr.length){
            return arr;
        }
        Random random = new Random();
        int l = 0,r = arr.length;
        // [l,r)
        while (true){
            int rd = random.nextInt(r-l)+l;
            swap(arr,rd,l);

            // (l,tl)<V,(tg,r)>V,[i,tg]未处理,[tl,i) = V
            int i=l+1,tl = l+1,tg=r-1;
            while (i<=tg){
                if(arr[i]>arr[l]){
                    swap(arr,tg,i);
                    tg--;
                }else if(arr[i]<arr[l]){
                    swap(arr,tl,i);
                    tl++;
                    i++;
                }else {
                    i++;
                }
            }
            tl--;
            swap(arr,tl,l);
            // [l,tl)<V,(tg,r)>V,[tl,tg] = V
            tg++;
            // [l,tl)<V,[tg,r)>V,[tl,tg) = V

            if(k>=tl&&k<=tg){
                return Arrays.copyOf(arr,k);
            }else if(k<tl){
                r = tl;
            }else {
                l = tg;
            }
        }
    }
    private void swap(int[] arr,int i,int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
